1. Field of the Invention
The invention relates to a data coding device and method, and a data decoding device and method; and more particularly it relates to an improved coding and decoding device and methods for color pixel data.
2. Description of Related Art
Since pixel data contain large quantities of information, if the pixel data are processed in its existent state, a large amount of memory capacity is required, the communication rate becomes slower, and impractical. Furthermore, compression technology of the picture image data becomes extremely important. Therefore compression technology for each type of data has been developed and brought into existence from the prior art.
In recent years, as one method of data compression, attention has been paid to technology which makes use of entropy coders and decoders. As one of the entropy coding and decoding technologies, utilization is made for example of arithmetic coding and decoding technology. The concept of this technology is revealed for example in laid open patent publication Sho 62-185413, laid open patent publication 63-74324, and laid open patent publication 63-76525.
FIG. 11 shows a conventional data coding system 50 and a data decoding system 60 which utilizes this type of technology.
The data coding system 50 includes a line buffer 51, and an entropy coder 52. The input color pixel data 100A is input to the line buffer 51 and the entropy coder. The color pixel data 100A, as shown in FIG. 12, in every instance is input as chronological pixel data in a horizontal chronological scan.
The line buffer 51, as a reference pixel generation means, forms reference pixel data an, bn, cn, and dn, relative to the coded object image pixel Xn from the pre-input picture image data 100A. In other words, the line buffer 51 records the continuous record of the n line divisions at the time of scanning. Also, following the inputting of each of the color pixel data 100A of the coded object pixel Xn, the series of pixel data formed from the immediately previous pixel dn, and the peripheral pixels an, bn, and cn are recorded as reference pixel data 110 and output to the entropy coder 52.
The entropy coder 52 is formed for example using the arithmetic coding and (Hoffman) coding methods. Also, the reference pixel data 110 is used as state signals, and the object color pixel data 100A is converted into coded data 200, and output.
The data decoding system 60 is formed to include line buffer 61, and entropy decoder 62. In this instance, the line buffer 61 and the entropy decoder 62 are formed so as to provide a decoded output of the input coded data 200 with entirely the opposite process of the line buffer 51 and the entropy encoder 52 of the data coding system 50.
In this manner, the data coding system 50 and the data decoding system 60 utilize algorithms, which are entirely opposite to each other, to encode the color pixel data 100A into coded data 200, and to decode the coded data 200 into the color pixel data 100B for output. Accordingly, the system can be broadly utilized for each type.
With this type of system, the reference pixel data 110 is utilized by the entropy coder 52, and the entropy decoder 62 state signals. If the number of states, i.e., the number of reference pixels, is great, then the data compression ratio is improved. In other words, when utilization is made of the arithmetic coding method or the Hoffman coding method to realize the entropy coder 52 and the decoder 62, if there is a great bias in the occurrence probability of the 0 and 1 symbols, the data compression ratio can be increased. This is because, with the entropy coding technology, short coding data is (allocated) to the input data having a high occurrence probability, and relatively long coding data is allocated to the input data having low generation probability.
In order to obtain a great bias in the symbol generation (occurrence) probability, according to the prior art, the input data has been classified (grouped) into several states prior to the coding. This is because, without classification (grouping), a good compression ratio cannot be obtained. For example, according to the conventional method shown in FIG. 11, utilization was made of line buffers 51 and 61 to form the reference pixel data. This was input as the state signal used for classification (grouping), into the entropy coder 52 and the entropy decoder 62. Also, the entropy coder 52 and the entropy decoder 62 classify (group) the input data through the utilization of the state signals, thereby accomplishing coding and decoding. In other words, the occurrence probability for each state of the reference pixel data is calculated, and short coding data is given to combinations having high generation (occurrence) probability. By this means, the compression ratio of the data can be increased.
However, with the entropy coder 52 and the entropy decoder 62, it is necessary for the number of coded parameter tables to correspond to the number of states of the reference pixel data. For this reason, to the extent that the number of reference pixels for increasing the compression ratio is great, the coding parameter table is great. Because of this, there is the problem that the entropy coder 52 and the entropy decoder 62 will big, and high in cost.
Assuming that the color pixel data is composed from 4 bit data for each pixel, and that the number of pixels of the reference pixel data 110 is 4, the number of states for coding and decoding parameter tables corresponds to the states of 4 pixels.times.4 bits=16 bit, namely the number of states becomes 2. For this reason, the parameter table must have 65,536 patterns for 2.sup.16 states. As the number of the reference pixels increases by one, the coding and decoding parameter table becomes extremely large, and it is understood that the hardware composing the entropy coder 52 and the entropy decoder 62 become large in scale. Furthermore, also the object pixel is composed of 4 bits, i.e., 4 planes, and a one-bit signal is applied to each plane. As a result, 16 patterns of color values are obtained with 4 bits. Therefore, the parameter table must have a magnitude of 65536.times.16 (see FIG. 13).
To overcome this problem, a method has been proposed for calculating the tendency of the occurrence probability of the color symbols of the object pixels, and for allocating short coded data to a symbol which occurs with a high probability, to improve the compression ratio (laid open patent publication 6-276041). This laid open patent publication also discloses a technology for making the parameter table smaller corresponding to the number of degenerated states compressed in the entropy coder 52 and the entropy decoder 62.
The feature of the system for degenerating the number of states as disclosed in laid open patent publication 6-276041 is shown in FIG. 14. The reference pixel data 110 is input as state signals into the entropy coder 52 and the entropy decoder 62 in the same manner as with the prior art data coder system 50 and the data decoder system 60. The feature is, at the time of its input, the state signal 140 is produced by means of the state degenerator 53, and 63 which degenerates the reference pixel data 110 outputted from the line buffers 51 and 61.
The state degenerators 53 and 63 are designed so as to degenerate the input reference pixel data 110 into the state signal 140 which has a relatively small number of bits, and to output it to the corresponding entropy coder 52 and entropy decoder 62. Furthermore, the predictor 54 and 64, are provided to store, in its memory, a color ranking table (the particulars of which are described in the laid open patent publication 6-276041), which is stored in memory in order to convert the color pixel data into the corresponding color rank, based on the probability of occurrence of the color symbol.
Degeneration is an operation for grouping a number of the original states into less numbers of states. Grouping is executed by selecting combinations of states such that the entropy (the average amount of data to display one symbol) of the post-grouping becomes minimum. Identification bits are assigned to the number of the post-grouping states. This becomes the state signal 140.
In the degeneration table utilized in the state degenerators 53 and 63, the relationship between the combination pattern of the color symbol of the reference pixel data 110 and the degeneration data is defined. There is a method, utilizing this degeneration table, for converting the combination pattern of the color symbol of the input reference pixel data 110 into the degeneration data and output.
FIG. 15 shows an example of a degeneration operation which is accomplished based on this method. In this instance, in order to simplify the explanation, an explanation is provided of an example in which Markov model which is formed from the three pixels A, B, and C, is used as a reference pixel pattern relative to the coded object pixel X, as shown in FIG. 15(A).
As shown in FIG. 15(A), when the reference pixels are formed from the three pixels, the combination pattern of the color symbols become five ways as shown in FIG. 15(B). In other words, the patterns are classified into the five patterns, namely, a pattern in which three of the pixel color symbols entirely conform, three patterns in which two of the three color symbols conform, and a patterning which all of the pixel color symbols are different.
Thus, by using the table shown in FIG. 15(B) as the degeneration tables of the state degenerators 53 and 63, 2.sup.12 patterns of the pixel state, which are all the possible combinations of the three pixels, can be reduced to the five states S1-S5 shown in FIG. 15(B). This allows the reference pixel data 110 to be effectively degenerated, and the number of states of the entropy coder 52 can be greatly reduced.
The general method for arithmetic coding and decoding accomplished in this manner is already described in detail in pgs. 26-44 and pgs. 44-50 of Single Pixel Coding Standard JBIG (International Standard ISO-IEC11544); however, in this instance, it will be simply explained hereafter as the premise of the present invention.
An example of the arithmetic coding type entropy coder 52 utilized in FIG. 11 is shown in FIG. 16. Since the composition of the arithmetic decoder type entropy decoder 62 is substantially the same as the composition of the coder 52, an explanation of it is omitted.
The entropy coder 52 includes the arithmetic calculator 55, and the RAM 56 which functions as a state storage. Within RAM 56, the state parameter table is written which is necessary for determination of the symbol generation (occurrence) number probability essential to coding. The state parameters are specified by the input state signal. To the table of the parameter specified by the state signal, the arithmetic calculator 55 outputs the data at the time of renewal of the calculator parameters as the readout address. Then, the RAM data specified by the readout address is output to the arithmetic calculator 55. The arithmetic calculator 55 converts the input color rank data 120 into coded data 200, on the basis of such input data, and output it.
With such prior art technology, the compression ratio becomes relatively high. However, since the bias of the occurrence probability of the data is not sufficiently taken into account, the compression ratio is fairly low in comparison with the theoretical compression ratio. In addition, since there is substantial degeneration as well, the parameter table also becomes small, and the entropy coder 52 and the entropy decoder 62 are also made smaller. However, only the reference pixels are taken into consideration, and grouping is not conducted to the states of the object pixel for prediction. Because of this, in terms of decoding, time taken for defining the object pixels, i.e., time taken for determining the final value for each plane to which each of the bits of the object pixels is allocated, is not used in the prediction operation, which makes the decoding rate poor.
Additionally, at the time of accomplishing compression or expansion (de-compression), the calculated time according to the RAM or ROM is extended, in addition to the delay in the interconnects, and decoding may not occur on time relative to the input of the data. Because of this, high cost, high speed ROM or RAM becomes necessary, and the entropy decoder 62 also remains in its existent state, in large scale and high cost form.